use std::borrow::Borrow;

/**
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
// Definition for singly-linked list.
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

impl ListNode {
    #[inline]
    fn new(val: i32) -> Self {
        ListNode {
            next: None,
            val,
        }
    }
}

fn main() {
    println!("Hello, world!");
    let l1 = Some(Box::new(
        ListNode {
            val: 2,
            next: Some(Box::new(
                ListNode {
                    val: 4,
                    next: Some(Box::new(
                        ListNode::new(3))),
                })),
        }));
    let l2 = Some(Box::new(
        ListNode {
            val: 5,
            next: Some(Box::new(
                ListNode {
                    val: 6,
                    next: Some(Box::new(
                        ListNode::new(4))),
                })),
        }));
    let mut res = add_two_numbers(l1, l2);

    let mut r = &mut res;
    while r.is_some() {
        print!("{:?}", r.as_mut().unwrap().val);
        r = &mut r.as_mut().unwrap().next;
    }
}

/**
解法一
*/
pub fn add_two_numbers(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    let (mut p, mut q) = (&l1, &l2);
    add_two_numbers_with_shift(p, q, 0)
}

pub fn add_two_numbers_with_shift(l1: &Option<Box<ListNode>>, l2: &Option<Box<ListNode>>, shift: i32) -> Option<Box<ListNode>> {
    let sum = if l1.is_some() { l1.as_ref().unwrap().val } else { 0 } + if l2.is_some() { l2.as_ref().unwrap().val } else { 0 } + shift;
    let mut p = if l1.is_some() { &l1.as_ref().unwrap().next } else { &l1 };
    let mut q = if l2.is_some() { &l2.as_ref().unwrap().next } else { &l2 };
    let (this_num, next_shift) = (sum % 10, if sum >= 10 { 1 } else { 0 });
    Some(Box::new(ListNode {
        val: this_num,
        next: if p.is_some() || q.is_some() || next_shift != 0 { add_two_numbers_with_shift(p, q, next_shift) } else { None },
    }))
}

/**解法2*/
pub fn add_two_numbers2(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    let (mut p, mut q) = (&l1, &l2);
    let mut head: Option<Box<ListNode>> = None;
    let mut cur = &mut head;

    let mut shift = 0; // 进位
    while p.is_some() || q.is_some() {
        let d = if p.is_some() { p.as_ref().unwrap().val } else { 0 } +
            if q.is_some() { q.as_ref().unwrap().val } else { 0 } +
            shift;

        *cur = Some(Box::new(ListNode::new(d % 10)));
        cur = &mut cur.as_mut().unwrap().next;
        shift = d / 10;

        if p.is_some() { p = &p.as_ref().unwrap().next; }
        if q.is_some() { q = &q.as_ref().unwrap().next; }
    }

    if shift > 0 {
        *cur = Some(Box::new(ListNode::new(shift)));
    }

    head
}